#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void siftDown(int* arr, int n, int root, int end) {
    int child = root * 2 + 1;
    while (child < end) {
        if (child + 1 < end && arr[child + 1] > arr[child]) {
            child++;
        }
        if (arr[child] > arr[root]) {
            swap(&arr[child], &arr[root]);

            root = child;
            child = root * 2 + 1;
        } else {
            break;
        }
    }
}

void heapSort(int* arr, int n) {
    for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
        siftDown(arr, n, i, n);
    }

    for (int end = n - 1; end; end--) {
        swap(&arr[0], &arr[end]);
        siftDown(arr, n, 0, end);
    }
}

int main() {
    int arr[100];
    srand((unsigned int)time(NULL));

    int n = sizeof(arr) / sizeof(*arr);
    for (int i = 0; i < n; ++i) {
        arr[i] = rand() % 200;
    }

    heapSort(arr, n);

    for (int i = 0; i < n; i++) {
        printf("%d\t", arr[i]);
        if ((i + 1) % 10 == 0) {
            printf("\n");
        }
    }

    return 0;
}